package com.leecode;

import java.util.Arrays;

/**
 * 300. 最长上升子序列
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 * 我这题翻译的有毒,原题意思应该是
 * [10,101]
 * [9,101] or [9,18]
 * ...
 * [2,3,7,101] or [2,3,7,18]
 * 示例:
 *
 * 输入:
 * [10,9,2,5,3,7,101,18]    ---nums
 *   1,1,1,2,2,3,  4,4      ---dp
 * [10,9,2,5,3,7,101,6]
 *   1,1,1,2,2,3,  4,3
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 */
public class Leet300 {
	public static void main(String[] args) {
		new Leet300().lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18});
	}

	/**
	 * 经过一定刷题经验后,直觉告述我是dp
	 * 66%,94%
	 */
	public int lengthOfLIS(int[] nums) {
		if(nums==null)return 0;
		if(nums.length<=1)return nums.length;

		int max=1;
		int dpAdd=0;//dp[a]"应该,合适"加的值
		int[] dp=new int[nums.length];
		Arrays.fill(dp,1);//给数组每个元素赋值1,学到了!!
		int moveE=dp.length-1;//22.优化:效果不明显
		while(moveE>=1){
			if (nums[moveE - 1] < nums[moveE]) break;
			moveE--;
		}

		for(int a=1;a<=moveE;a++){//21.优化,需不需要更新到dp的未尾?不需要!!
			for(int apre=a-1;apre>=0;apre--){
//				if(nums[apre]<nums[a]){//11.bug:没想到,大意了
//					dp[a]+=dp[apre];
//					max=Math.max(max,dp[a]);
//					break;
//				}

				if (nums[apre] < nums[a]) {
					dpAdd=Math.max(dpAdd,dp[apre]);
				}
			}
			dp[a]+=dpAdd;
			max=Math.max(max,dp[a]);
			dpAdd=0;
		}
		return max;
	}

}
